﻿namespace LeetCodeProject._0001_1000._001_100._41_50._044;

public class Solution
{
    public bool IsMatch(string s, string p)
    {
        if (s == null)
            throw new ArgumentException(nameof(s));
        if (p == null)
            throw new ArgumentException(nameof(s));
        var cache = new byte[s.Length, p.Length];
        return IsMatch(s, 0, p, 0, cache);
    }

    private bool IsMatch(string s, int si, string p, int pi, byte[,] cache)
    {
        if (pi == p.Length)
            return si == s.Length;
        if (si < s.Length && pi < p.Length && cache[si, pi] != 0)
            return cache[si, pi] == 1;
        if (si > s.Length)
            return false;
        bool res;
        var pch = p[pi];
        if (pch == '*')
        {
            res = IsMatch(s, si, p, pi + 1, cache) || IsMatch(s, si + 1, p, pi, cache);
        }
        else
        {
            res = si < s.Length && (pch == '?' || pch == s[si]) && IsMatch(s, si + 1, p, pi + 1, cache);
        }

        if (si < s.Length)
            cache[si, pi] = (byte)(res ? 1 : 2);
        return res;
    }
}